RDAs based on RBESs are widely used in the development of computer applications for use in the fields of medicine, health, and financial services. In the United States, for example, fraud identification in credit card transactions is often done using RDAs based on RBESs. The market for RBES engines is currently estimated at approximately $300 Mil, and is expected to reach $500 Mil by 2013.
A classic example of an RDA or “rule-driven system” is a system of rules to make deductions or choices written in a high-level programming language. For example, an RDA might help a doctor choose the correct diagnosis based on a cluster of symptoms, or select tactical moves to play a game. RDAs based on RBESs allow program developers to represent programming logic using high-level rules described in declarative language (hereinafter referred to interchangeably as “RDA language” and “rule language”) without worrying about low-level details of the execution of individual rules. In order to allow developers to avoid these low-level details, in fact, rule execution logic and the high-level declarative nature of rules are often completely separated in rule development. In other words, in many cases, new rules may be added to existing RBESs without making laborious and error-prone changes to underlying low-level rule logic.
FIG. 1 shows an overview of the organization of an exemplary RDA. It is to be understood that FIG. 1 is merely for illustrative purposes and that FIG. 1 is not meant as an exhaustive display of RDA features. The RDA 100 includes a rule base 10 which includes a plurality of rules and data that represents a “knowledge” or “expertise” of the RDA. An inference engine 20 (hereinafter referred to interchangeably as “inference engine” or “RBES engine”) determines which rules from the rule base 10 are executed at any given time, as well as how to execute them. The inference engine 20 generally does not contain rules until they are added by developers of the RDA through a developer interface 30. Rather, the inference engine 20 generally contains only routines that specify how to execute rules and how to infer conclusions from results obtained from the execution of rules.
One of the major roles of the inference engine 20 is, for example, to determine which information, variables, and rules may be needed from the rule base 10 for the execution of a particular rule and to combine the information, variables, and rules in order to create new information and store the newly created information in a working memory 40. A user executes the RDA 100 through a user interface 50, as shown in FIG. 1.
Broadly, rules in RDA rule bases 10 may be instructions or commands that apply under certain conditions. Rules generally interact with variables, or “properties” (hereinafter, the terms “variable” and “property” may be used interchangeably in the context of the description of rules). For example, “A and B=>C” is a rule that may be “fired,” “triggered,” or “executed” (herein the terms “fired,” “triggered,” and “executed” may be used interchangeably) when values A and B are both present. Executing the rule stores a value C. The new value C generated by the rule may, for example, trigger the execution of other rules. Each of the triggered rules may produce new information, variables, or conditions, again possibly resulting in the execution of still more rules. In this way, the execution of a rule may lead to execution of a long chain of rules. Each of the executed rules may read from or write to variables in the system database. “Interferences” may arise when one rule in the execution chain alters a variable in a way that alters the execution of another rule.
When the conditions are such that more than one rule could be executed at a given time, different RBES engines may use different techniques to determine the execution sequence. Because of the different execution sequences, different RBESs may lead to different states or outcomes resulting from the same inputs. A simple example illustrates this in the case of two rules, rules 1 and 2:if (PK==3){PN==2}  rule 1:if (PK==3){PN==3}  rule 2:
“Operand1==operand2” is a relational expression using the operator “==” to determine if operand1 and operand2 are equal. If operand1 and operand2 are equal, the expression “operand1==operand2” returns a logical “TRUE.” If operand1 and operand2 are not equal, the expression “operand1==operand2” returns a logical “FALSE.”
When the condition “PK==3” is true, both rules 1 and 2 will fire. However, executing rule 1 first and rule 2 second will lead to a final condition where PN is equal to 3, while executing rule 2 first and rule 1 second will lead to a final condition in which PN is equal to 2. Therefore, different execution sequences, which vary from RBES to RBES, may result in different outcomes. Moreover, each rule may write to variables in a database that other rules use during execution. Different execution sequences may then cause rules to execute differently, again leading to different outcomes.
It is possible to test RDAs for interferences and to use the test results to eliminate the interferences. Much of the current effort in testing RDAs centers on checking the rules for consistency, completeness, and redundancy. The testing may often be made difficult by the sheer number of rules and the inherent complexity of their interaction. For example, if an RDA includes k rules that may be fired n times in response to a particular condition, each of these rules may contain up to kn distinct states or outcomes. Moreover, the inherent non-deterministic quality of RBESs adds to the complexity and resultant difficulty in testing.
RDA testing routines usually detect: (1) rule conflicts and (2) incompleteness. Conflicts arise when multiple rules have premises that may hold at the same time, shared variables, and/or other interactions that can cause inconsistent results. As described herein, conflicts may create non-deterministic behavior in a rule-driven application that may lead to different results when the application is executed. Incompleteness is a situation in which none of the rules in the rule base 10 can fire.
When two or more rules fire at the same time, it can be difficult or impossible to predict the actual execution sequence without a protracted analysis. To verify that a particular condition leading to a conflict is reached, it may be necessary to examine a large number of components and possible scenarios. This is because different rule execution sequences may lead to the condition in a plurality of different ways. Therefore, a way to identify possible conflicts arising in RDAs that deals with this complexity is desirable.